{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Nth Node From End of List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list #two-pointers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表 #双指针"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: removeNthFromEnd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除链表的倒数第 N 个结点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个链表，删除链表的倒数第&nbsp;<code>n</code><em>&nbsp;</em>个结点，并且返回链表的头结点。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg\" style=\"width: 542px; height: 222px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2,3,4,5], n = 2\n",
    "<strong>输出：</strong>[1,2,3,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1], n = 1\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>head = [1,2], n = 1\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中结点的数目为 <code>sz</code></li>\n",
    "\t<li><code>1 &lt;= sz &lt;= 30</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= sz</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能尝试使用一趟扫描实现吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-nth-node-from-end-of-list](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-nth-node-from-end-of-list](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]\\n2', '[1]\\n1', '[1,2]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        curr = head\n",
    "        num = 0\n",
    "        while curr!= None:\n",
    "            num += 1\n",
    "            curr = curr.next\n",
    "        m = num - n\n",
    "        if m == 0:\n",
    "            return head.next\n",
    "        curr = head\n",
    "        while m != 1:\n",
    "            curr = curr.next\n",
    "            m = m - 1\n",
    "        curr.next = curr.next.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        tem = head\n",
    "        num_tem = n\n",
    "        #如果链表为空就直接返回None\n",
    "        if not head:\n",
    "            return None\n",
    "        # 得到倒数第n个节点，注意倒数第一个是最后一个，\n",
    "        # 所以控制的num_tem是大于1，这样两个tem节点的位置就是第n个位置，\n",
    "        # 数组的位置是从0开始的，也就是数组的n-1位\n",
    "        while tem and num_tem > 1:\n",
    "            tem = tem.next\n",
    "            num_tem -= 1\n",
    "        tem_n = tem\n",
    "        head_n = head\n",
    "        pre = head\n",
    "        #在得到第n个位置后，一直循环到最后一位，那么head_n就是倒数第n个元素，\n",
    "        # pre是第n-1个元素（n>1)\n",
    "        while tem_n.next:\n",
    "            tem_n = tem_n.next\n",
    "            pre = head_n\n",
    "            head_n = head_n.next\n",
    "        #如果倒数第n个元素就是第1个元素，直接返回第二个元素开始即可\n",
    "        if head_n==head:\n",
    "            return head.next\n",
    "        #否则只需要倒数第n-1个元素的下一个元素是倒数第n+1元素即可\n",
    "        else:\n",
    "            pre.next = head_n.next\n",
    "            return head\n",
    "\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        if not head:\n",
    "            return None\n",
    "    \n",
    "        first = head\n",
    "        second = head\n",
    "            \n",
    "        for i in range(n):\n",
    "            if second.next:\n",
    "                second = second.next\n",
    "            else:\n",
    "                return None\n",
    "        \n",
    "        while second.next:\n",
    "            first = first.next\n",
    "            second = second.next\n",
    "        if first == head:\n",
    "            return head.next\n",
    "        elif first.next == second:\n",
    "            first.next = None\n",
    "            return head\n",
    "            \n",
    "        else:\n",
    "            temp = first.next\n",
    "            first.next = first.next.next\n",
    "            temp.next = None\n",
    "            return head\n",
    "        \"\"\"\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        p, q = head, head\n",
    "\n",
    "        for _ in range(n):\n",
    "            q = q.next\n",
    "\n",
    "        if q is None:\n",
    "            return head.next\n",
    "\n",
    "        while q.next is not None:\n",
    "            p = p.next\n",
    "            q = q.next\n",
    "\n",
    "        p.next = p.next.next\n",
    "\n",
    "        return head\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: 'ListNode', n: 'int') -> 'ListNode':\n",
    "        List = ListNode(0)\n",
    "        List_o = List\n",
    " \n",
    "        first = head\n",
    "        second = head\n",
    "        for i in range(n):\n",
    "            second = second.next\n",
    "            \n",
    "        while second != None:\n",
    "            List.next = first\n",
    "            List = List.next\n",
    "            second = second.next\n",
    "            first = first.next\n",
    "            \n",
    "            print(List.val)\n",
    "            \n",
    "        List.next = first.next\n",
    "        \n",
    "        return List_o.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head, n):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type n: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if head is None:\n",
    "            return \n",
    "        #双指针流\n",
    "        count=1\n",
    "        temp=head\n",
    "        pre_node=None\n",
    "        while count<n:\n",
    "            temp=temp.next\n",
    "            count+=1\n",
    "        node=head\n",
    "        while temp.next:\n",
    "            pre_node=node\n",
    "            temp=temp.next\n",
    "            node=node.next\n",
    "        if pre_node is None:\n",
    "            return head.next\n",
    "        else:\n",
    "            pre_node.next=node.next\n",
    "            return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        '''\n",
    "        p = ListNode(None)\n",
    "        p.next = head\n",
    "        q = head\n",
    "        l = 0\n",
    "        while q!=None:\n",
    "            l += 1\n",
    "            q = q.next\n",
    "        l -= n\n",
    "        q = p\n",
    "        while l>0:\n",
    "            l -= 1\n",
    "            q = q.next\n",
    "        q.next = q.next.next\n",
    "        return p.next\n",
    "        '''\n",
    "        p = ListNode(None)\n",
    "        p.next = head\n",
    "        first, second = p, p\n",
    "        for i in range(n+1):\n",
    "            first = first.next\n",
    "        while first!=None:\n",
    "            first = first.next\n",
    "            second = second.next\n",
    "        second.next = second.next.next\n",
    "        return p.next\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        p = ListNode(None)\n",
    "        p.next = head\n",
    "        q = head\n",
    "        l = 0\n",
    "        while q!=None:\n",
    "            l += 1\n",
    "            q = q.next\n",
    "        l -= n\n",
    "        q = p\n",
    "        while l>0:\n",
    "            l -= 1\n",
    "            q = q.next\n",
    "        q.next = q.next.next\n",
    "        return p.next\n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if head.next == None or head == None:\n",
    "            return None\n",
    "        p = head\n",
    "        while True:\n",
    "            pp = p\n",
    "            for i in range(n):\n",
    "                pp = pp.next\n",
    "            if pp == None:\n",
    "                return head.next\n",
    "            if pp.next == None:\n",
    "                if n == 1:\n",
    "                    p.next = None\n",
    "                else:\n",
    "                    pp = p.next.next\n",
    "                    p.next = pp\n",
    "                break\n",
    "            p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        count=0\n",
    "        p=head\n",
    "        q=head\n",
    "        while p!=None:\n",
    "            p=p.next\n",
    "            count+=1\n",
    "        num=count-n\n",
    "        c=1\n",
    "        if(num==0):\n",
    "            head=head.next\n",
    "            return head\n",
    "        while q!=None:\n",
    "            if c==num:\n",
    "                q.next=q.next.next\n",
    "            q=q.next\n",
    "            c+=1\n",
    "        return head\n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        end=head\n",
    "        del_node=None\n",
    "        for _ in range(n):\n",
    "            end=end.next\n",
    "        while end is not None:\n",
    "            end=end.next\n",
    "            if not del_node:\n",
    "                del_node=head\n",
    "            else:\n",
    "                del_node=del_node.next\n",
    "        if not del_node:\n",
    "            return head.next\n",
    "        else:\n",
    "            del_node.next=del_node.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        fast, delete = head,head\n",
    "        curr = head\n",
    "        num = 0\n",
    "        while curr!=None:\n",
    "            curr = curr.next\n",
    "            num+=1\n",
    "        \n",
    "        \n",
    "        if num == n :\n",
    "            head = head.next\n",
    "            return head\n",
    "        for _ in range(n+1):\n",
    "            fast = fast.next\n",
    "       \n",
    "        while fast:\n",
    "            fast = fast.next\n",
    "            delete = delete.next\n",
    "        delete.next = delete.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        \n",
    "        thead = ListNode(-1)\n",
    "        thead.next = head\n",
    "        pre,post = None,thead\n",
    "        for i in range(n):\n",
    "            post = post.next\n",
    "        pre = thead\n",
    "        while(post.next):\n",
    "            post = post.next\n",
    "            pre = pre.next\n",
    "        pre.next = pre.next.next\n",
    "        return thead.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        # 假设长度为N，要删除倒数第k个，既要删除正数第N-k个\n",
    "        # 用A和B2个指针，A先走k步，之后A和B同时走\n",
    "        # A从k出发到达终点N需要走N-k步，此时B正好停在N-k的位置，即B为待删除的位置\n",
    "        A = B = head\n",
    "        # A先走k步\n",
    "        for _ in range(n):\n",
    "            A = A.next\n",
    "        # A,B同时走，直到A到达终点\n",
    "        prev_B = None\n",
    "        while A != None:\n",
    "            A = A.next\n",
    "            prev_B = B\n",
    "            B = B.next\n",
    "        if not prev_B:  # 删除的是第一个元素，即倒数第n个元素\n",
    "            return head.next\n",
    "        else:\n",
    "            prev_B.next = B.next\n",
    "            return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dummy = ListNode(0, head)\n",
    "        first = head\n",
    "        second = dummy\n",
    "        for i in range(n):\n",
    "            first = first.next\n",
    "        \n",
    "        while first:\n",
    "            first = first.next\n",
    "            second = second.next\n",
    "        \n",
    "        second.next = second.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        k = 0\n",
    "        p = head\n",
    "        q = head\n",
    "        while p:\n",
    "            if k==n:\n",
    "                r=q\n",
    "                q=q.next\n",
    "            else:\n",
    "                k+=1\n",
    "            p=p.next\n",
    "        if q==head:\n",
    "            return head.next\n",
    "        r.next=q.next\n",
    "        del q\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        front=ListNode(0)\n",
    "        front.next,fast,slow=head,front,front\n",
    "        while(n or fast):\n",
    "            if n:fast,n=fast.next,n-1\n",
    "            else:\n",
    "                fast=fast.next\n",
    "                slow=slow.next if fast else slow\n",
    "        slow.next=slow.next.next \n",
    "        return front.next "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if head.next is None:\n",
    "            return None\n",
    "        quick = head\n",
    "        for j in range(n):\n",
    "            quick = quick.next\n",
    "        if quick is None:\n",
    "            return head.next\n",
    "        prev = head\n",
    "        while prev and quick:\n",
    "            print(prev.val, quick.val)\n",
    "            if quick.next is None:\n",
    "                prev.next = prev.next.next\n",
    "                break\n",
    "            prev = prev.next\n",
    "            quick = quick.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        nhead = head\n",
    "        if head.next is None:\n",
    "            return head.next\n",
    "\n",
    "        pscan = head\n",
    "        pt = nhead\n",
    "        \n",
    "        cnt = 0\n",
    "        while pscan:\n",
    "            pscan = pscan.next\n",
    "            if cnt > n:\n",
    "                pt = pt.next\n",
    "            cnt += 1\n",
    "            print(cnt,pt.val)\n",
    "\n",
    "        if cnt == n:\n",
    "            return head.next\n",
    "        else:\n",
    "            d = pt.next\n",
    "            d = d.next\n",
    "            pt.next = d\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        p = point = ListNode(0)\n",
    "        point.next = head\n",
    "         \n",
    "        count = 0\n",
    "        while p:\n",
    "            p = p.next\n",
    "            count +=1\n",
    "        point2 = point\n",
    "        nn = 0\n",
    "        while point2:\n",
    "            print(nn,n,count,count-nn)\n",
    "            if count-nn == n+1:\n",
    "                point2.next = point2.next.next\n",
    "            nn+=1\n",
    "            point2 = point2.next\n",
    "        return point.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        dumpy=ListNode(next=head)\n",
    "        fast=dumpy\n",
    "        slow=dumpy\n",
    "        for i in range(n):\n",
    "            fast=fast.next\n",
    "        while fast.next:\n",
    "            fast=fast.next\n",
    "            slow=slow.next\n",
    "        \n",
    "        #删除倒数第k个节点\n",
    "        slow.next=slow.next.next\n",
    "        return dumpy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        slow,fast = dummy,dummy\n",
    "\n",
    "        for _ in range(n):\n",
    "            fast = fast.next\n",
    "        \n",
    "        while(fast.next):\n",
    "            slow,fast = slow.next,fast.next\n",
    "        \n",
    "        slow.next = slow.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        empty_node = ListNode(val=None,next=None)\n",
    "        empty_node.next=head\n",
    "        len = 1\n",
    "        ptr1 = empty_node\n",
    "        while ptr1.next != None:\n",
    "            ptr1 = ptr1.next\n",
    "            len= len+1\n",
    "        if len==2 : return None\n",
    "        zhenghsu = len-n\n",
    "        if zhenghsu ==1 :\n",
    "            return head.next\n",
    "        ptr = empty_node\n",
    "        for i in range(1,zhenghsu):\n",
    "            ptr = ptr.next\n",
    "        ptr.next = ptr.next.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        dummy = ListNode(0, head)\n",
    "        node1 = head\n",
    "        for i in range(n):\n",
    "            node1 = node1.next\n",
    "        node2 = dummy\n",
    "        while node1:\n",
    "            node1 = node1.next\n",
    "            node2 = node2.next\n",
    "        node2.next = node2.next.next\n",
    "\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    \n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        # 递归 从底下往上删除\n",
    "        \n",
    "        cnt = [0]    \n",
    "        def deletehelper(head, n):\n",
    "            if not head.next: # 最后一个节点\n",
    "                cnt[0] += 1 # 倒数第一格\n",
    "                return head\n",
    "            \n",
    "            rethead = deletehelper(head.next, n) # 先到底\n",
    "            \n",
    "            cnt[0] += 1 # 回升的时候加\n",
    "            if cnt[0] == n+1: # 删除点的上一个点\n",
    "                to_connect = head.next.next\n",
    "                head.next.next = None\n",
    "                head.next = to_connect\n",
    "            return rethead\n",
    "\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        deletehelper(dummy, n)\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        dummy_node = ListNode(next=head)\n",
    "\n",
    "        slow=fast = dummy_node\n",
    "\n",
    "        for i in range(n+1):\n",
    "            fast = fast.next\n",
    "\n",
    "        \n",
    "        while fast:\n",
    "            slow = slow.next\n",
    "            fast = fast.next\n",
    "\n",
    "        slow.next = slow.next.next\n",
    "\n",
    "        return dummy_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:\n",
    "        if head.next == None:\n",
    "            return None\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        begin, end = dummy, dummy.next\n",
    "        while n:\n",
    "            end = end.next\n",
    "            n -= 1\n",
    "        \n",
    "        while end:\n",
    "            begin = begin.next\n",
    "            end = end.next\n",
    "        begin.next = begin.next.next\n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # dummy = ListNode(0)\n",
    "        # dummy.next = head\n",
    "        # begin, end = dummy, dummy.next\n",
    "        # pos = 1\n",
    "        # while pos < n:\n",
    "        #     end = end.next\n",
    "        #     pos += 1\n",
    "        # while end.next:\n",
    "        #     end = end.next\n",
    "        #     begin = begin.next\n",
    "        # begin.next = begin.next.next\n",
    "\n",
    "        # return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        res_list = []\n",
    "        while head:\n",
    "            res_list.append(head.val)\n",
    "            head = head.next\n",
    "        del res_list[len(res_list) - n]\n",
    "\n",
    "        res = None\n",
    "        for i in res_list[::-1]:\n",
    "            res = ListNode(i, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:\n",
    "        #快指针先走n-1步，\n",
    "        dummy_head = ListNode()\n",
    "        dummy_head.next = head\n",
    "        fast = dummy_head\n",
    "        slow = dummy_head\n",
    "        if head.next == None and n == 1:\n",
    "            return None\n",
    "        for i in range(0,n):\n",
    "            fast = fast.next\n",
    "        while fast.next != None:\n",
    "            fast = fast.next\n",
    "            slow = slow.next\n",
    "        slow.next = slow.next.next\n",
    "        return dummy_head.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
